This invention relates generally to computers and more particularly to video graphics processing involving the generation of geometric primitives.
FIG. 1 illustrates a schematic block diagram of a computing system 10 that includes a central processing unit 12, a chipset 14, system memory 16, a video graphics circuit 18, and a display 20. The video graphics circuit 18 includes a raster engine 22 and a frame buffer 24. The system memory 16, for processing video graphics data, includes geometry software 26 and texture maps 28. The display 20 may be a CRT display, LCD display, or other type of computer display.
To process video graphic data, the central processing unit 12 executes the geometry software 26 to produce geometric primitives. The geometric primitives include attributes for each vertex of a triangle, where a plurality of triangles constitutes an object to be displayed. The attributes of the geometric primitives include spatial coordinates, texture coordinates, color data, and specular color data. Upon receiving the geometric primitives, the raster engine generates pixel data from the geometric primitives for each vertex and stores the pixel data in frame buffer 24. In essence, the raster engine 22 generates pixel data for each pixel within a given triangle based on the geometric primitives of the vertices of the triangle. Once the raster engine has generated pixel data for an entire frame, or field, the raster engine retrieves the pixel data from the frame buffer 24 and provides it to display 20 for display. During the generation of pixel data, if the geometric primitives include a texture coordinate, the raster engine 22 retrieves texture information from texture maps 28.
The geometry software 26 uses a Sutherland-Hodgeman Polygon Clipping Algorithm to produce the geometric primitives. In general, the Sutherland-Hodgeman Polygon Clipping Algorithm compares the vertices of each triangle of an object with a plane of a clip volume or one of a plurality of user defined planes. FIG. 2 illustrates a clip volume, which includes six planes. As shown, the planes include a near plane 32 (which corresponds to an eye plane), a far plane 34 (which corresponds to the screen), a top plane 36, a bottom plane 38, a left-side plane 40, and a right side plane 42.
If the plane does not clip (i.e., intersect the triangle), another plane is compared. The Sutherland-Hodgeman Polygon Clipping Algorithm compares each plane with the triangle to determine whether a plane clips the triangle. If none of the planes clip the triangle, the geometric primitives of the triangle corresponding to the three original vertices are provided to the raster engine. If, however, at least one plane intersects the triangle, the Sutherland-Hodgeman Polygon Clipping Algorithm determines a clipping distance from each vertices with respect to the clipping plane (e.g., the clipping distances may correspond to d1, d2, and d3). If a vertex is within the clip volume, the clipping distance will be positive, if a vertex is outside the clip volume, the clipping distance would be negative. A positive clipping distance has a xe2x80x9czeroxe2x80x9d clip code and a negative clipping distance has a xe2x80x9c1xe2x80x9d clip code.
Having obtained the clip codes and clipping distances, the Sutherland-Hodgeman Polygon Clipping Algorithm determines the new vertices for the clipped triangle. To begin the Sutherland-Hodgeman Polygon Clipping Algorithm utilizes a clip code table to determine an operation to be performed. The clip code table includes binary codes for previous and current vertices and the corresponding operation. The following is an example of the clip code table.
For a given triangle, V1, V2, and V3 represent the three original vertices. For a first clip code table look-up, V3 is the previous vertex and V1 is the current vertex. For a second look up, V1 is the previous vertex and V2 is the current vertex. For a third look up, V2 is the previous vertex and V3 is the current vertex. For example, if V1 and V2 have a xe2x80x9czeroxe2x80x9d clip code, and V3 has a xe2x80x9conexe2x80x9d clip code the three table look ups have a binary code of (1,0), (0,0), and (0,1). Thus, the operation for V3 to V1 will be to add the current vertex (e.g., V1) and calculate and add a new vertex (e.g., C0). The operation for V1 to V2 will be to add the current vertex (e.g., V2). The operation for V2 to V3 will be to calculate and add a new vertex (e.g., C1).
To calculate the spatial coordinates of the new vertices (e.g., C0 and C1), the Sutherland-Hodgeman Polygon Clipping Algorithm utilizes the homogenous vertex spatial coordinates (e.g., X, Y, Z, W) and the clipping distances. Such a calculation is process intensive. In addition to calculating the coordinates, the Sutherland-Hodgeman Polygon Clipping Algorithm determines the attributes (e.g., RGB color components, texture coordinates, etc.) for each of the new vertices.
As these values are calculated, they are stored in memory. Having stored these values, the Sutherland-Hodgeman Polygon Clipping Algorithm performs the same process for the next plane that clips the triangle and continues until all clipping planes have been processed. As one can imagine, the Sutherland-Hodgeman Polygon Clipping Algorithm requires a substantial amount of memory to store the attributes for all the vertices of a clipped triangle. For example, if each attribute is a 32 bit word, each vertex has 32 attributes, and there are 12 clipping planes, the memory requirement would be (12 plus 3)xc3x9732xc3x9732, which equals 2K bytes of memory. Note that the 12 plus 3 corresponds to 12 clipping planes plus the three for the original vertices. Since a triangle is rarely clipped by more than a few planes, most of this memory is not used.
Once the attributes for the final vertices have been obtained, the geometry software 26 then performs lighting and/or texture processing for the clipped triangle. As is known, the lighting function determines the particular lighting effect that is to be rendered. The lighting effect may be from a single light source or a plurality of light sources wherein the light sources is either close to the object or at a diffused distance. The texture coordinate processing includes texture transformation or texture generation. Since the lighting and/or texture mapping functions are dependent on the finalized vertices of the clipped triangle, these processes must be performed after the clipping process. As such, they are done in a serial manner.
Therefore, a need exists for a method and apparatus that provides for parallel processing of geometric primitives and reduces memory requirements such that a hardware geometry engine may be practically implemented.